package day02;

public class BinarySortTree <E extends Comparable<E>>{
    private Node root;//根节点
    @Override
    public String toString() {
//        1.判断root是否为null，若为null，返回[]
        if(root==null)
            return "[]";
//        若有元素，使用中序遍历，将遍历得到的元素拼接到StringBuilder中
        StringBuilder builder= new StringBuilder("[");
//        使用中序遍历，将元素拼接入builder中
        root.middleOrder(builder);
//        对builder中最后的,进行处理
        builder.deleteCharAt(builder.lastIndexOf(","));
        return builder.append("]").toString();
    }
    /**
     * 用于查找元素对应的节点，如果找不到，则返回null
     */
    public Node get(E e){
        if(root==null)
            return null;
//        从root开始判断每个节点是否为查找的节点
       return root.get(e);
    }
    /**
     * 定义add()用于添加元素
     */
    public boolean add(E e){
//        判断root是否为null
        if(root==null){
            root =new Node(e);
            return true;
        }
        return root.append(e);
    }
//定义内部类Node表示节点对象
     class Node{
        private E data;//节点中保存的元素
        private Node left;//左子树
        private Node right;//右子树
//        含参构造方法--将给出的元素封装成节点对象
    Node(E e){
        data = e;
    }
    public boolean append(E e) {
//        先判断元素e的值是否与目标节点相等，如果相等，返回添加失败
        if(e.compareTo(data)==0){
            return false;
        }
//        判断是否小于目标节点，小于就添加到节点的左子树上
          else if (e.compareTo(data)<0){
//              先判断left是否为null，若为null，新元素封装成节点赋值给left
            if(left==null){
                left = new Node(e);
                return true;
            }else return left.append(e);
        }else {//e大于目标节点的元素，添加到右子树
              if (right==null){
                  right =new Node(e);
                  return true;
              }else return right.append(e);
        }
    }

    public void middleOrder(StringBuilder builder) {
//        先遍历左子树
        if(left!=null){
            left.middleOrder(builder);
        }
//        获取根节点的元素，拼接入builder
        builder.append(data).append(",");
//        遍历右子树
        if(right!=null){
            right.middleOrder(builder);
        }
    }
    //用于判断当前节点是否为目标元素e对应的节点
        public Node get(E e) {
            if(e.compareTo(data)==0){
                return this;
            }else if (e.compareTo(data)<0){
                if (left==null){
                    return null;
                }
            return left.get(e);
            }else {
                if (right==null)
                    return null;
              return   right.get(e);
            }
        }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
}
